﻿// 4555. 公共子序列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>


using namespace std;
/*

https://www.acwing.com/problem/content/4558/
给定两个由大小写字母构成的字符串，请你计算并输出它们的最长公共子序列的长度。

输入格式
输入包含多组测试数据。

每组数据占一行，包含两个字符串。

输出格式
每组数据输出一行结果，一个整数，表示最长公共子序列的长度。

数据范围
输入最多包含 100
 组数据。
输入字符串的长度范围 [1,1000]。

输入样例：
abcfbc         abfcab
programming    contest
abcd           mnp
输出样例：
4
2
0
*/


const int N = 1010;
char a[N], b[N];
int dp[N][N];

void solve() {
	memset(dp, 0, sizeof dp);
	a[0] = '@'; b[0] = '#';

	int al = strlen(a);
	int bl = strlen(b);

	for (int i = 1; i <= al; i++) {
		for (int j = 1; j <= bl; j++) {
			if (a[i] == b[j]) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	printf("%d\n", dp[al - 1][bl - 1]);

	return;
}


int main()
{
	while (~scanf("%s%s", a + 1, b + 1)) {
		solve();
	}


	return 0;
}

